//https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
//相交链表
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

typedef struct ListNode ListNode;

ListNode* find(ListNode* curA, ListNode* curB, ListNode* headA, ListNode* headB)
{
    int count = 0;
    while(curA->next)
    {
        curA = curA->next;
        count++;
    }

    if(curA != curB)
    return NULL;

    while(count--)
    {
        headA = headA->next;
    }

    while(headA != headB)
    {
        headA = headA->next;
        headB = headB->next;
    }

    return headA;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;
    while(curA->next && curB->next)
    {
        curA = curA->next;
        curB = curB->next;
    }

    if(curB->next == NULL)
    {
        return find(curA, curB, headA, headB);
    }
    else
    {
        return find(curB, curA, headB, headA);
    }
}